package first

/*
	请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

	若队列为空，pop_front 和 max_value需要返回 -1

	示例 1：

	输入:
	["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
	[[],[1],[2],[],[],[]]
	输出:[null,null,null,2,1,2]
	示例 2：

	输入:
	["MaxQueue","pop_front","max_value"]
	[[],[],[]]
	输出:[null,-1,-1]

	限制：

	1 <= push_back,pop_front,max_value的总操作数<= 10000
	1 <= value <= 10^5

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
type MaxQueue struct {
	Queue     []int
	AssQqueue []int
}

func Constructor1() MaxQueue {
	return MaxQueue{
		Queue:     make([]int, 0),
		AssQqueue: make([]int, 0),
	}
}

func (this *MaxQueue) Max_value() int {
	if len(this.Queue) == 0 || len(this.AssQqueue) == 0 {
		return -1
	}
	return this.AssQqueue[0]
}

func (this *MaxQueue) Push_back(value int) {
	this.Queue = append(this.Queue, value)
	for len(this.AssQqueue) != 0 && value > this.AssQqueue[len(this.AssQqueue)-1] {
		this.AssQqueue = this.AssQqueue[:len(this.AssQqueue)-1]
	}
	this.AssQqueue = append(this.AssQqueue, value)
}

func (this *MaxQueue) Pop_front() int {
	if len(this.Queue) == 0 {
		return -1
	}
	top := this.Queue[0]
	this.Queue = this.Queue[1:]
	if top >= this.AssQqueue[0] {
		this.AssQqueue = this.AssQqueue[1:]
	}
	return top
}

/**
 * Your MaxQueue object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Max_value();
 * obj.Push_back(value);
 * param_3 := obj.Pop_front();
 */
